package com.cheung.leetcode.day;

import  org.junit.jupiter.api.Test;

import java.util.TreeMap;

/**
 * @BelongsProject : java-leetcode
 * @BelongsPackage : com.cheung.leetcode.day
 * @Author :  cheungming
 * @CreateTime : 2024-07-09 21:52:56
 * @Description : 每日 一题
 * @Version : 1.0
 */
public class Code3102Test {

    public int minimumDistance(int[][] points) {
        // 曼哈顿距离 (x1,y1),(x2,y2) = |x1-x2|+|y1-y2|
        // 上述曼哈顿距离 = max{|(x1+y1) - (x2+y2)|,|(x1-y1)-(x2-y2)|} 即切比雪夫距离

        // 设两个有序的集合 sx,sy 分别存储 x-y 和 x+y
        TreeMap<Integer, Integer> sx = new TreeMap<>();
        TreeMap<Integer, Integer> sy = new TreeMap<>();

        // 遍历所有点
        for (int[] point : points) {
            int x = point[0];
            int y = point[1];
            sx.put(x - y, sx.getOrDefault(x - y, 0) + 1);
            sy.put(x + y, sy.getOrDefault(x + y, 0) + 1);
        }

        // 遍历所有点，计算切比雪夫距离
        int res = Integer.MAX_VALUE;
        for (int[] point : points) {
            int x = point[0];
            int y = point[1];
            // 删除当前点
            sx.put(x - y, sx.get(x - y) - 1);
            if (sx.get(x - y) == 0) {
                sx.remove(x - y);
            }

            sy.put(x + y, sy.get(x + y) - 1);
            if (sy.get(x + y) == 0) {
                sy.remove(x + y);
            }

            // 根据有序集合，计算最大的切比雪夫距离，然后比较结果取最小值
            res = Math.min(res, Math.max(sx.lastKey() - sx.firstKey(), sy.lastKey() - sy.firstKey()));
            // 添加当前点
            sx.put(x - y, sx.getOrDefault(x - y, 0) + 1);
            sy.put(x + y, sy.getOrDefault(x + y, 0) + 1);
        }

        return res;
    }

    @Test
    public void test1() {
        assert minimumDistance(new int[][]{{3, 10}, {5, 15}, {10, 2}, {4, 4}}) == 12;
    }

}
